The present invention relates to a system and method for dynamic allocation of a resource and, in particular, it concerns a system to dynamically designate a priority for a resource request and to allocate a resource, partially filling or completely filling the request; the system and method of the present invention improve the optimization of a Bandwidth On Demand (BOD) satellite communication system.
Resource allocation systems have the following goals: maximization of resource availability, maximization of resource utility, minimization of cost, and maximization of revenue to resource providers. Maximization of resource availability requires that users not be refused access to the resource in times of need. Maximization of utility requires that when resources are scarce, the most important requests be filled first. Minimization of costs requires that resource requests be filled with minimum investment in resources and overhead. Maximization of revenue to resource providers requires that the resource be provided to the maximum number of users willing to pay for use of the resource.
For example, in a satellite communication network, multiple users of differing characteristics simultaneously communicate with a satellite over various radio frequency bands. Conventional satellite communication systems schedule a frequency band to a single user for a set time. Thus, the scheduled user may communicate with the satellite via the scheduled band at the time scheduled and may not communicate by any other band. Resource scheduling guarantees resource availability to a particular user, but resource scheduling does not maximize availability because a scheduled band is unavailable to an unscheduled user even when the scheduled user does not need the scheduled band. Similarly, resource scheduling does not minimize cost because a user must schedule and pay for exclusive access to more resources than are actually needed. Similarly, scheduling does not maximize revenue or utility because many important paying users are refused access to the scheduled resource.
To make more efficient use of limited satellite resources in fixed bandwidth DAMA systems, a central controller schedules available frequency bands of one or more communication satellites. First, a user requests a frequency band from the central controller. Then the controller allocates a frequency band to the user and communicates to the user the allocated band. When the user no longer needs the allocated band, the user informs the controller and the controller reallocates the band to a new user. The user is only charged for resources that are used and unneeded resources are immediately made available to fill new requests.
The above-described fixed bandwidth DAMA system is well suited to a network where users require a fixed bandwidth. An example of a user requiring a fixed bandwidth is a mobile telephone for voice communication. On the other hand, modern communication networks include broadband users whose bandwidth requirement may not be fixed. Broadband communication is much more efficient than multiple narrow band communication because a broadband user of an n-band frequency range is capable of communicating information 2n times as fast as a user of a narrow one-band frequency range. For example, a broadband ground station can relay calls of sixteen cellular phones using the same bandwidth that would be required by four mobile phones making direct access to the satellite.
Broadband users require a continuous frequency band. For example in a system with a continuous set of frequency bands numbered from one to ten, a broadband user of four frequency bands may be assigned bands 4, 5, 6 and 7 but the broadband user may not be assigned bands 4, 5, 7 and 8 because the latter four bands skip band 6 and are, therefore, not continuous.
The bandwidth required by a broadband user often is not fixed but depends on the number of individuals accessing the broadband resource at a given time. For example a local area network (LAN) includes a plurality of individual computers. Typically the LAN accesses the Internet through a broadband satellite ground station called a remote gateway. The number of individuals accessing data from the Internet on the LAN determines the bandwidth required by the remote gateway. Similarly the bandwidth required by a cellular telephone ground station is dependent on the number of active callers in the region of the station.
Prior art systems for optimizing resource allocation of broadband resources are called Bandwidth On Demand (BOD) systems and include the following:
Dimitrijevic et al. (U.S. Pat. No. 5,978,363) describes a system and method for multidimensional resource scheduling. The system of Dimitrijevic is first come first serve. A new user requests any quantity of requested resources from a central controller. If the requested resources are not allocated to a current user then the request is filled, and the requested resources are allocated to the new user. After allocation to the new user, the requested resources are not available to any other user. If a new user requests a resource that is allocated to a current user, the request is blocked without recourse. When the controller is informed that a current user no longer needs the allocated resources, the controller de-allocates the allocated resources. Deallocation frees resources for reallocation to a new user. Each user is billed according resource use. Resource use is defined as the quantity of resources allocated to the user multiplied by the time over which the resources were allocated to the user. By allowing resources to be scheduled and unscheduled according to need, the Dimitrijevic et al. system optimizes the quantity of resources used. The only limit to resource use in the Dimitrijevic system is the absolute availability of the resource and the willingness to pay of the user. The Dimitrijevic system results in severe limitations on resource availability. Specifically, a few users may block a large quantity of resources. Therefore, in order to deliver reliable access, the Dimitrijevic et al. system requires a very high resource to user ratio.
Garner (U.S. Pat. No. 6,058,307) improves availability of a resource, which is a frequency range, by categorizing potential users by absolute priority. Each user is given an absolute priority. A requesting user of a first priority requests resources. If the requested resources are available in a reserve pool, then the reserve resources are allocated to the requesting user. If the requested resources are not available in the reserve pool, a search is conducted for unassigned resources in active pools. If the requested resources can be made available by switching resources in an active pool then current users are switched and freed resources are transferred to the reserve pool and assigned to the requesting user. If the request cannot be filled from unallocated resources, then the controller assesses the priority level of each current user. When there are insufficient unallocated resources and there is a current user of lower priority level than the requesting user, then the low priority level resources of the current user are preempted. The preempted low priority level resources of the current user are then reallocated to the new user. When there are insufficient unallocated resources and the priority level of all current users is greater or equal to the priority level of the requesting user, the request is blocked. Garner further categorizes resources into multiple pools and allows a user to have an arbitrary priority level in each pool. Thus the Garner system allows priority users improved access to resources as compared to the Dimitrijevic system. This improves the utility of the Garner system because when resources are scarce, resources are preferentially allocated to high priority users. Furthermore, the Garner system offers lower cost service to low priority users because the system can accept large numbers of low priority users at low resource to user ratio and at a low cost. Priorities are an absolute user parameter in the Garner system. For a given resource pool, a particular user has a single priority level which applies to all resource use of the user in the resource pool. When a particular user wishes to have reliable access to resources in a desired resource pool the particular user must request high priority for all resource in that pool and pay a correspondingly high price for all resource requests in the desired pool. A user who chooses cheaper low priority service risks having service cut off in the middle of a transmission. Resource allocation to users of similar priority level is first come first serve like the system of Dimitrijevic et al. Therefore the Garner system can only give reliable service to a small number of high priority users. Furthermore, it is difficult to optimize resource allocation in the Garner system because there is a complex set of multiple pools and the division of analog resources in each pool may take on an unlimited number of configurations.
Ogasawara et al. (U.S. Pat. No. 6,070,052) improves on the Garner system of allocating frequency resources by rationalizing the switching of active resources. Thus frequency bands are allocated according to current need as in the Gardner system, and frequency bands are assigned such that users can expand their bandwidth with a minimum amount of switching. Nevertheless the resources priority algorithm of Ogasawara is similar to the algorithm of Gardner.
Thus, resource allocation systems in the prior art assign resources absolutely. In the prior art a request for resources may only be filled or blocked completely. In the prior art resource allocation systems, there is no limit to the quantity of resources that may be requested by a user. Therefore a few current users can block access to a large quantity of resources. None of the prior art resource allocation systems can guarantee resource access to a large number of users. Furthermore, prior art frequency allocation systems allocate frequencies in analog quantities. Analog quantities can be divided into an infinite number of configurations and the large number of configurations complicates optimization of decision. Even when frequency is discretized, bandwidths and free frequency bands can have arbitrary sizes seriously complicating the matching of requests for bandwidth to available free bands.
There is therefore a widely recognized need for, and it would be highly advantageous to have, a resource allocation system that allows reliable access to a large number of users and without unnecessarily preventing access to unused resources. Furthermore, it is desirable that the system allows efficient optimization of resource assignment.